package vn.edu.vnu.sort;

import java.util.ArrayList;

import android.os.Bundle;
import android.app.Activity;
import android.content.Intent;
import android.view.View;
import android.view.View.OnClickListener;
import android.view.ViewGroup.LayoutParams;
import android.widget.Button;
import android.widget.LinearLayout;
import android.widget.ScrollView;
import android.widget.TextView;

public class Result extends Activity {
	ArrayList<String> result;
	static int time = 0;

	@Override
	public void onCreate(Bundle savedInstanceState) {
		super.onCreate(savedInstanceState);
		setContentView(R.layout.activity_result);
		ScrollView scrollView = (ScrollView) findViewById(R.id.scrollView1);
		LinearLayout linearLayout = new LinearLayout(this);
		linearLayout.setOrientation(LinearLayout.VERTICAL);
		TextView tv2 = (TextView) findViewById(R.id.textView2);
		TextView tv3 = (TextView) findViewById(R.id.textView3);
		Button btn = (Button) findViewById(R.id.button1);
		btn.setOnClickListener(new OnClickListener() {

			public void onClick(View arg0) {
				// TODO Auto-generated method stub
				Intent intent = new Intent();
				intent.setClassName("vn.edu.vnu.sort",
						"vn.edu.vnu.sort.Choosing");
				startActivity(intent);
			}
		});
		result = new ArrayList<String>();

		Intent localIntent = getIntent();
		Bundle myBundle = localIntent.getExtras();
		ArrayList<Integer> myList = myBundle.getIntegerArrayList("list");
		int algrithmNumber = myBundle.getInt("alg");

		String chosen = null;
		if (algrithmNumber == 1) {
			chosen = "The Bubble sort is chosen";
			tv3.setText("Bubble sort result");
			this.bubbleSort(myList);
		} else if (algrithmNumber == 2) {
			chosen = "The Quick sort is chosen";
			tv3.setText("Quick sort result");
			this.quickSort(myList, 0, myList.size() - 1);
		} else {
			chosen = "The Heap sort is chosen";
			tv3.setText("Heap sort result");
			this.heapSort(myList);
		}
		tv2.setText(chosen);

		TextView[] tx = new TextView[result.size()];
		for (int i = 0; i < result.size(); i++) {
			tx[i] = new TextView(this);
			tx[i].setLayoutParams(new LayoutParams(LayoutParams.FILL_PARENT,
					LayoutParams.WRAP_CONTENT));
			tx[i].setPadding(20, 0, 20, 0);
			tx[i].setText(result.get(i) + "");
			linearLayout.addView(tx[i]);
		}
		scrollView.addView(linearLayout);
	}

	private void bubbleSort(ArrayList<Integer> myList) {
		int time1 = 0;
		if (myList.size() == 1) {
			result.add("Pass " + ++time1);
			result.add("( " + myList.get(0) + " )" + " ( " + myList.get(0) + " )");
		} else {
			boolean loop = true;
			while (loop) {
				loop = false;
				result.add("Pass " + ++time1);
				for (int i = 0; i < (myList.size() - 1); i++) {
					String temp1 = "(";
					String str = "";
					for (int k = 0; k < myList.size(); k++) {
						temp1 = temp1 + " " + myList.get(k);
					}

					if (myList.get(i) > myList.get(i + 1)) {
						str = ", Swap since " + myList.get(i) + ">" + myList.get(i + 1);
						int swap = myList.get(i);
						myList.set(i, myList.get(i + 1));
						myList.set(i + 1, swap);
						loop = true;
					}

					temp1 += " )";
					String temp2 = "(";
					for (int k = 0; k < myList.size(); k++) {
						temp2 = temp2 + " " + myList.get(k);
					}
					temp2 += " )";
					result.add(temp1 + " " + temp2 + str);
				}
			}
		}
	}
	
	private int partition(ArrayList<Integer> myList, int left, int right)

	{
		if(myList.size() - 1 == right && left == 0) 
			time = 0;
		result.add("Pass " + ++time);
		int i = left, j = right;
		int tmp;
		int pivot = myList.get((left + right) / 2);
	     
		while (i <= j) {
			String temp1 = "(";
			String str = "";
			for (int k = 0; k < myList.size(); k++) {
				temp1 = temp1 + " " + myList.get(k);
			}
			while (myList.get(i) < pivot)
				i++;
			while (myList.get(j) > pivot)
				j--;
			if (i < j) {
				if(myList.get(i) != myList.get(j)) {
					str = ", Swap since " + myList.get(i) + ">" + myList.get(j);
					tmp = myList.get(i);
					myList.set(i, myList.get(j));
					myList.set(j, tmp);
				}
				i++;
				j--;
			} else if (i == j) {
				i++;
				j--;
			}
			temp1 += " )";
			String temp2 = "(";
			for (int k = 0; k < myList.size(); k++) {
				temp2 = temp2 + " " + myList.get(k);
			}
			temp2 += " )";
			result.add(temp1 + " " + temp2 + str);
		};    
		return i;
	}
	
	private void quickSort(ArrayList<Integer> myList, int left, int right) {
	      int index = partition(myList, left, right);

	      if (left < index - 1)
	            quickSort(myList, left, index - 1);
	      if (index < right)
	            quickSort(myList, index, right);
	}
	
	private void heapSort(ArrayList<Integer> myList) {
		if (myList.size() == 1) {
			result.add("( " + myList.get(0) + " )" + " ( " + myList.get(0) + " )");
		} else {
		int i, s, f, elt, v;
		int n = myList.size();
		for (i = 1; i < n; i++) {
			String temp1 = "(";
			for (int k = 0; k < myList.size(); k++) {
				temp1 = temp1 + " " + myList.get(k);
			}
			temp1 += " )";
			elt = myList.get(i);
			s = i;
			f = (s - 1) / 2;
			while (s > 0 && myList.get(f) < elt) {
				myList.set(s, myList.get(f));
				s = f;
				f = (s - 1) / 2;
			}
			myList.set(s, elt);
			String temp2 = "(";
			for (int k = 0; k < myList.size(); k++) {
				temp2 = temp2 + " " + myList.get(k);
			}
			temp2 += " )";
			result.add(temp1 + " " + temp2);
		}
		for (i = n - 1; i > 0; i--) {
			String temp1 = "(";
			for (int k = 0; k < myList.size(); k++) {
				temp1 = temp1 + " " + myList.get(k);
			}
			temp1 += " )";
			v = myList.get(i);
			myList.set(i, myList.get(0));
			f = 0;
			if (i == 1)
				s = -1;
			else
				s = 1;
			if (i > 2 && myList.get(2) > myList.get(1))
				s = 2;
			while (s >= 0 && v < myList.get(s)) {
				myList.set(f, myList.get(s));
				f = s;
				s = 2 * f + 1;
				if ((s + 1) <= i - 1 && myList.get(s) < myList.get(s+1))
					s = s + 1;
				if (s > (i - 1))
					s = -1;
			}

			myList.set(f, v);
			String temp2 = "(";
			for (int k = 0; k < myList.size(); k++) {
				temp2 = temp2 + " " + myList.get(k);
			}
			temp2 += " )";
			result.add(temp1 + " " + temp2);
		}
	}
	}
}
